//
// Created by zhuanding on 2023/6/4.
//

#include <cstdio>
#include "../01-preface/Status.h"

#define MAXSIZE 50  // 定义顺序表最大长度


typedef struct {
    int data[MAXSIZE];  // 存储顺序表中的元素
    int length;   // 存储顺序表的长度
} SqList;  // 顺序表类型定义


void swap(int &a, int &b){
    int temp=a;
    a=b;
    b=temp;
}

/*
 * 初始化，创建一个长度为空的顺序表
 */
void InitList(SqList &L) {
    L.length = 0;
}

/*
 * 顺序表的遍历
 */
void TraverseList(SqList L) {
    for (int i = 0; i < L.length - 1; ++i) {
        printf("%d\t", L.data[i]);
    }
}

bool ListEmpty(SqList L) {
    if (L.length == 0)
        return true;
    else
        return false;
}


int ListLength(SqList L) {
    return L.length;
}

/*
 * 初始条件：顺序表已经存在，并且1<=p<=L.length+1
 * 操作结果：在顺序表L中第p个位置之前插入新的元素e，表长加一
 * 操作步骤：
 * 1.判断插入位置p是否合法；
 * 2.将插入位置p当前的元素及之后的元素都后移；
 * 3.在空出来的位置p上放入元素e；
 * 4.表长加一。
 */
bool ListInsert(SqList &L, int p, int e) {
    if (p < 1 || p > L.length + 1 || L.length >= MAXSIZE) return false;   // 1. 判断插入位置p是否合法
    for (int i = L.length; i >= p; i--) {    // 2. 将插入位置p当前的元素及之后的元素都后移
        L.data[i] = L.data[i - 1];
    }
    L.data[p - 1] = e;   // 3. 在空出来的位置p上放入元素e
    L.length++;   // 4. 表长加一
    return true;
}

/*
 * 初始条件：顺序表已经存在，并且1<=p<=L.length.
 * 操作结果：删除顺序表L中第p个元素，并用e返回删除元素的值
 * 操作步骤：
 * 1.判断p值合法；
 * 2.将第p个元素的值用e保存；
 * 3.p之后的元素前移；
 * 4.表长减一。
 */
bool ListDelete(SqList &L, int p, int &e) {
    if (p < 1 || p > L.length) return false;
    e = L.data[p - 1];
    for (int i = p; i < L.length; i++) {
        L.data[i - 1] = L.data[i];
    }
    L.length--;
    return true;
}

/*
 * 初始条件：顺序表存在且非空，1<=p<=L.length
 * 操作结果：查找顺序表中第p个元素，并且用e返回第p个元素的值
 */
bool ListGet(SqList L, int p, int &e) {
    if (L.length <= 0 || p < 1 || p > L.length) return false;
    e = L.data[p - 1];
    return true;
}

/*
 * 初始条件：顺序表存在且非空
 * 操作结果：查找顺序表中第1个元素值为e的元素的位序，并且返回其位序
 */
int ListLocate(SqList L, int e) {
    int p;
    if (L.length <= 0) return false;
    for (
            p = 0;
            p < L.
                    length;
            p++) {
        if (L.data[p] == e) {
            return p + 1;
        }
    }
    return true;
}

/*
 * --------------------------------王道课后练习题-------------------------------
 */

/*
 * 01.从顺序表中删除具有最小值的元素（假设唯一）并由函数返回被删除元素的值。空出的位置由最后一个元素填补，若顺序表为空，则显示出错信息并退出运行。
 * 初始条件：顺序表存在且非空
 * 操作步骤：定义两个分别变量保存最小值和对应的数组下标，循环遍历表中的所有元素找出最小值，删除最小值元素并用最后元素填补，
 */
bool ListDeleteMin(SqList &L, int &min) {
    if (L.length == 0) return false;
    min = L.data[0];
    int p = 0;  // 记录最小值和对应的数组下标
    for (int i = 1; i < L.length; i++) {
        if (L.data[i] < min) {
            min = L.data[i];
            p = i;
        }
    }// 循环顺序表中的元素找出最小值和其对应的下标
    L.data[p] = L.data[L.length - 1];   // 用表中最后一个元素填补最小元素的空缺位置
    L.length--;   // 表长减一
    return true;
}

/*
 * 02.设计一个高效算法，将顺序表L的所有元素逆置，要求算法的空间复杂度为O(1)。
 * 初始条件：顺序表存在且非空
 * 操作步骤：扫描顺序表L的前半部分元素，对于元素L.data[i](0<=i<L.length/2)，将其与后半部分的对应元素L.data[L.length-i-1]进行交换。
 */
void ListReverse(SqList &L) {
    int temp;  // 定义辅助变量
    for (int i = 0; i < L.length / 2; i++) {
        temp = L.data[i];
        L.data[i] = L.data[L.length - i - 1];
        L.data[L.length - i - 1] = temp;
    }
}

/*
 * 03.对长度为n的顺序表L，编写一个时间复杂度为O(n),空间复杂度为O(1)的算法，该算法删除线性表中所有值为x的数据元素。
 * 初始条件：顺序表存在且非空
 * 操作步骤：
 * 解法1：用k记录顺序表L中不等于x的元素个数（即需要报错的元素个数），扫描时将不等于x的元素移动到下标k的位置，并更新k值。扫描结束后修改L的长度。
 * 解法2：用k记录顺序表L中等于x的元素个数，变扫描边统计k，并将不等于x的元素前移k个位置。扫描结束后修改L的长度。
 */
void del_x_1(SqList &L, ElemType x) {
    int k = 0;   // 记录值不等于x的元素个数，也是不等于x的元素所要重新放置的位置下标
    for (int i = 0; i < L.length; i++) {
        if (L.data[i] != x) {
            L.data[k] = L.data[i];
            k++;
        }
    }
    L.length = k;
}


void del_x_2(SqList &L, ElemType x) {
    int k = 0;   // 记录等于x的元素个数
    for (int i = 0; i < L.length; i++) {
        if (L.data[i] == x)
            k++;
        else
            L.data[i - k] = L.data[i];   // 当前元素前移k个元素
    }
    L.length = L.length - k;         // 顺序表长度减少
}

/*
 * 04.从有序顺序表中删除其值在给定值s与t之间（要求s＜t）的所有元素，若s或t不合理或顺序表为空，则显示出错信息并退出运行
 * 初始条件：顺序表存在且非空（有序一般指递增序列）
 * 操作步骤：现寻找值大于或等于s的第一个元素（第一个删除的元素），然后寻找值大于t的第一个元素（最后一个删除的元素的下一个元素），
 *          要将这个这段元素删除，只需直接将后面的元素前移、
 */
bool Del_s_t(SqList &L, ElemType s, ElemType t) {
    int i, j;
    if (s >= t || L.length == 0) return false;
    for (i = 0; i < L.length && L.data[i] < s; i++);  // 寻找值大于或等于s的第一个元素
    if (i >= L.length) return false;  // 所有元素均小于s，返回
    for (j = i; j < L.length && L.data[j] <= t; j++);  // 寻找值大于t的第一个元素
    for (; j < L.length; i++, j++)
        L.data[i] = L.data[j];
    L.length = i;
    return true;
}


/*
 * 05.从顺序表中删除其值在给定值s与t之间（包含s和t，要求s＜t）的所有元素，若s或t不合理或顺序表为空，则显示出错信息并退出运行
 * 初始条件：顺序表存在且非空
 * 操作步骤：从前往后扫描顺序表L，用k记录下元素值在s到t之间元素的个数（初始时k=0）。对于当前扫描的元素，若其值不在s到t之间，则前移k个位置；否则执行k++。
 *         由于这样每个不在s到t之间的元素仅移动一次，因此算法效率高。
 */
bool Del_s_t2(SqList &L, ElemType s, ElemType t) {
    int k = 0, i;
    if (L.length == 0 || s >= t) return false;   // 初始条件
    for (i = 0; i < L.length; i++) {
        if (L.data[i] >= s && L.data[i] <= t)
            k++;
        else
            L.data[i - k] = L.data[i];   // 当前元素前移k个位置
    }
    L.length -= k;   // 长度减小
    return true;
}


/*
 * 06.从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不同
 * 初始条件：顺序表存在且非空
 * 操作步骤：有序顺序表，值相同的元素一定在连续的位置上，用类似于直接插入排序的思想，初始时将第一个元素视为非重复的有序表。之后一次判断后面的元素
 *          是否与前面非重复有序表的最后一个位置相同，若相同，则继续向后判断，若不同，则插入前面的非重复有序表的最后位置，直到判断到表尾为止。
 */
bool Delete_duplicated(SqList &L) {
    if (L.length == 0) return false;
    int i, j;   // i存储第一个不相同的元素，j为工作指针
    for (i = 0, j = 1; j < L.length; j++)
        if (L.data[i] != L.data[j])   // 查找下一个与上一个元素值不同的元素
            L.data[++i] = L.data[j];   // 找到后，将元素前移
    L.length = i + 1;   // 修改表长
    return true;
}
/*
 * 若将本题的有序表改为无序表，可以使用散列表实现，时间复杂度为O(n)。
 */


/*
 * 07.将两个有序表合并成一个新的有序表，并由函数返回结果顺序表。
 * 初始条件：两个有序表存在且非空
 * 操作步骤：按顺序依次取下两个有序表中的元素进行比较，将较小的元素存入新的顺序表中。直到一个表为空，将还有元素的有序表剩下的元素加入新表的后面。
 */
bool Merge(SqList A, SqList B, SqList &C) {
    // 将两个有序表A和B合并成一个新的有序表C
    if (A.length + B.length > MAXSIZE) return false;   // 此处MAXSIZE也可以替换成C.maxSize,即在结构体中存储了表最大长度
    int i = 0, j = 0, k = 0;
    while (i < A.length && j < B.length) {   // 循环，两两比较，小的存入结果表
        if (A.data[i] < B.data[j])
            C.data[k++] = A.data[i++];
        else
            C.data[k++] = B.data[j++];
    }
    while (i < A.length)
        C.data[k++] = A.data[i++];
    while (i < B.length)
        C.data[k++] = B.data[j++];
    C.length = k;
    return true;
}

/*
 * 08.已知一维数组A[m+n]中一次存放两个线性表(a1,a2,...,am)和(b1,b2,...,bn)。编写一个函数，将数组中两个顺序表位置互换，
 *    即将(b1,b2,...,bn)放在(a1,a2,...,am)前面。
 * 操作步骤：1.先将数组A原地逆置，在对前n个元素和后m个元素分别使用逆置。
 */
bool Reverse(ElemType A[], int left, int right, int arraySize) {
    if (left >= right || right >= arraySize) return false;
    int mid = (left + right) / 2;
    for (int i = 0; i < mid - left; i++) {
        ElemType temp = A[left + i];
        A[left + i] = A[right - i];
        A[right - i] = temp;
    }
    return true;
}

void Exchange(ElemType A[], int m, int n, int arraySize) {
    Reverse(A, 0, m + n - 1, arraySize);
    Reverse(A, 0, n - 1, arraySize);
    Reverse(A, n, m + n - 1, arraySize);
}

/*
 * 09. 线性表(a1,a2,a3,...,an)中的元素递增有序且按顺序存储于计算机内。要求设计一个算法，完成用最少时间在表中查找数值为x的元素。若找到，
 * 则将其与后继元素位置相交换，若找不到，则将其插入表中并使表中元素仍递增有序。
 * 操作步骤：题设要求"用最少的时间在表中查找数值为x的元素"，使用折半查找。
 */
void SearchExchangeInsert(int A[], int x) {
    int n = MAXSIZE,i;  // n是数组长度
    int low = 0, high = n - 1, mid;  // low和high指向数组的下界和上界的下标
    while (low <= high) {
        mid = (low + high) / 2; // 取中间数,向下取整
        if(x==A[mid]) break;  // 找到x，退出循环
        else if(A[mid]<x) low = mid+1;  // 到中点mid的右半部去查
        else high=mid-1;   // 到中点mid的左半部去查
    }   // 循环完之后，low==high
    if (A[low] == x && mid != n - 1){  // 查找成功并x不是最后一个元素（最后一个元素不存在与其后继交换的操作）
        swap(A[low], A[low+1]);     // 交换x和其后继元素位置
    }
    if(low>high){  // 查找失败，插入元素x
        for(i=n-1; i>high; i--)  // 后移元素
            A[i+1] = A[i];
        A[i+1]=x;  // 插入x
    }
}

/*
 * 10. 【2010统考】设将n(n>1)个整数存放到一维数组R中。设计一个在时间和空间两方面都尽可能高效的算法。将R中保存的序列循环左移p（0<p<n）个位置，
 * 即将R中的数据由（x0，x1，...，xn-1）变换为（xp，xp+1，...，xn-1，x0，x1，...，xp-1）。
 * 操作步骤：可讲问题视为把数组ab转换成ba（a代表数组前p个元素，b代表数组中余下的n-p个元素）。先将a逆置得到a^(-1)b,再将b逆置得到a^(-1)b^(-1)，
 * 最后将整个a^(-1)b^(-1)逆置得到(a^(-1)b^(-1))^(-1)=ba.
 * 操作步骤2：借助辅助数组来实现。创建大小为p的辅助数组S，将R中前p个整数依次暂存在S中，同时将R中后n-p个整数左移，然后将S中暂存的p个数依次放回到
 * R中的后续单元。事件复杂度为O(n)，空间复杂度为O(p).
 */
void Reverse(int R[], int from, int to){
    int i, temp;
    for(i=0;i<(to-from+1)/2; i++){
        temp = R[from+i];
        R[from+i] = R[to-i];
        R[to-i] = temp;  // swap(R[from+i], R[to-i]
    }
}

void Converse(int R[], int n, int p){
    Reverse(R, 0, p-1);  // O(p/2)
    Reverse(R, p, n-1);  // O((n-p)/2)
    Reverse(R, 0, n-1);   // O(n/2)
}
// 整个算法是事件复杂度为O(n)、空间复杂度为O(1)

/*
 * 11. 【2011统考】一个长度为L（L>=1)的升序序列S，处在第[L/2]（向上取整）个位置的数称为S的中位数。两个序列的中位数是含有他们所有元素的升序序列的中位数。
 * 现有两个等长升序序列A和B，试设计一个在时间和空间两方面尽可能高效的算法，找出两个序列A和B的中位数。
 * 操作步骤：1、使用归并排序将两个等长升序序列合并成一个升序序列；2、返回第[2L/2]个位置的数
 */
//void Merge_array(int A[], int B[], int C[]){
//
//}
//int Search_middle(int A[], int B[], int L){
//    int C[2*L];
//    Merge();
//}


/*
 * 主函数，用来测试算法
 */
int main() {
    SqList L;
    InitList(L);
    return 0;
}